package Leetcode.每日一题;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * @Author: kirito
 * @Date: 2024/4/16 12:08
 * @Description:
 * 尽量减少恶意软件的传播
 * 困难
 * 相关标签
 * 相关企业
 * 给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
 *
 * 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
 *
 * 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
 *
 * 如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
 *
 * 请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
 *
 *
 *
 * 示例 1：
 *
 * 输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
 * 输出：0
 * 示例 2：
 *
 * 输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
 * 输出：0
 * 示例 3：
 *
 * 输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
 * 输出：1
 *
 *
 * 提示：
 *
 * n == graph.length
 * n == graph[i].length
 * 2 <= n <= 300
 * graph[i][j] == 0 或 1.
 * graph[i][j] == graph[j][i]
 * graph[i][i] == 1
 * 1 <= initial.length <= n
 * 0 <= initial[i] <= n - 1
 * initial 中所有整数均不重复
 */

public class minMalwareSpread {
    /**
     * 我们可以分别考虑每一个连通分量：
     *
     * 如果其中没有感染节点，那么无需考虑；
     * 如果其中恰好有一个感染节点，移除该节点可以使得最终感染的节点数减少，减少的值即为该连通分量的大小；
     * 如果其中有超过一个感染节点，那么无论移除哪一个节点，剩下的那个（那些）节点总会感染连通分量中的所有节点，同样无需考虑。
     * 因此，我们可以首先使用深度优先搜索 / 广度优先搜索 / 并查集的方法求解出所有的连通分量，需要记录的值为：
     *      每一个节点所在的连通分量的编号，以及；
     *      每一个连通分量的大小。
     * 随后，我们遍历所有的感染节点，并使用一个哈希表记录每个连通分量中感染节点的数目。
     *
     * 1    1   0
     * 1    1   0
     * 0   0   1
     *
     *  0   1
     * @param graph
     * @param initial
     * @return
     */
    public int minMalwareSpread(int[][] graph, int[] initial) {
        // 获取图的行数，即节点数量
        int n = graph.length;
        // 初始化一个长度为n的数组，用于存储每个节点的集群ID
        int[] ids = new int[n];
        // 创建一个HashMap，用于存储集群ID和该集群大小的映射
        Map<Integer, Integer> idToSize = new HashMap<Integer, Integer>();
        // 初始化集群ID
        int id = 0;
        // 遍历所有节点
        for (int i = 0; i < n; ++i) {
            // 如果当前节点还没有分配集群ID
            if (ids[i] == 0) {
                // 分配新的ID并自增
                ++id;
                // 初始化集群大小为1
                int size = 1;
                // 使用广度优先搜索算法找到所有属于该集群的节点
                Queue<Integer> queue = new ArrayDeque<Integer>();
                queue.offer(i);
                ids[i] = id;
                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    // 遍历所有相邻节点
                    for (int v = 0; v < n; ++v) {
                        // 如果相邻节点还没有分配集群ID且两者之间有连接
                        if (ids[v] == 0 && graph[u][v] == 1) {
                            // 增加集群大小
                            ++size;
                            // 将相邻节点加入队列以便继续查找
                            queue.offer(v);
                            // 分配集群ID
                            ids[v] = id;
                        }
                    }
                }
                // 将集群大小存入HashMap
                idToSize.put(id, size);
            }
        }
        // 创建一个HashMap，用于存储集群ID和该集群内初始感染的节点数量映射
        Map<Integer, Integer> idToInitials = new HashMap<Integer, Integer>();
        // 遍历所有初始感染节点
        for (int u : initial) {
            // 更新每个集群内初始感染节点的数量
            idToInitials.put(ids[u], idToInitials.getOrDefault(ids[u], 0) + 1);
        }
        // 初始化最终答案，ans为最小感染扩散范围的节点，ansRemoved为该节点的感染扩散范围
        int ans = n + 1, ansRemoved = 0;
        // 遍历所有初始感染节点
        for (int u : initial) {
            // 计算移除当前节点后，其所在集群的感染扩散范围
            int removed = (idToInitials.get(ids[u]) == 1 ? idToSize.get(ids[u]) : 0);
            // 如果当前节点的感染扩散范围大于已记录的最小值，或相等且节点编号小于已记录的最小节点编号
            if (removed > ansRemoved || (removed == ansRemoved && u < ans)) {
                // 更新最小感染扩散范围的节点和其感染扩散范围
                ans = u;
                ansRemoved = removed;
            }
        }
        // 返回最小感染扩散范围的节点
        return ans;
    }


}
